#ifndef __U_TREE_SYSTEM_HPP__
#define __U_TREE_SYSTEM_HPP__

#include <ostream>
#include <queue>
#include <opencv2/core/core.hpp>
#include <libu/u-base.hpp>

namespace u {

    template <typename T, size_t D>
    class array_tree {
        public:
            virtual T get(size_t, size_t) = 0;
            virtual T get(size_t) = 0;
            virtual const T get(size_t, size_t) const = 0;
            virtual const T get(size_t) const = 0;
            virtual void set(T , size_t, size_t) = 0;
            virtual void set(T, size_t) = 0;
    };
    
    template <typename T>
    class btree: public array_tree<T, 2> {
        protected:
            std::vector<T> _data;
            size_t _depth;
    };
    
    template <typename T>
    class sbtree: public array_tree<T, 2> {
        private:
            std::vector<T> _data;
            size_t _depth;
            // level start from 0
            const size_t get_index(size_t level, size_t nth) const {
                return ((level + 1) * level / 2 + nth);
            }
            
        public:
            //overwrite if a class is derivided
            static size_t capacity(size_t depth) {
                return ((depth + 1) * depth / 2);
            }
            
            sbtree(size_t depth){
                size_t total = sbtree::capacity(depth);
                _data.resize(total);
                _depth = depth;
            }
            
            sbtree(T data, size_t depth) {
                size_t total = sbtree::capacity(depth);
                _data.resize(total);
                _data[0] = data;
                _depth = depth;
            }
        
            sbtree(const sbtree<T> &tree) {
                for (size_t i=0; i<tree.size() && i<_data.size(); ++i)
                    _data.push_back(tree[i]);
                _depth = tree.depth();
            }
            
            // level start from 0
            T get(size_t level, size_t index) {
                size_t i = get_index(level, index);
                assert(i < _data.size());
                return _data[i];
            }
            
            // level start from 0
            const T get(size_t level, size_t index) const {
                size_t i = get_index(level, index);
                assert(i < _data.size());
                return _data[i];
            }
            
            // level start from 0
            void set(T data, size_t level, size_t index) {
                size_t i = get_index(level, index);
                assert(i < _data.size());
                _data[i] = data;
            }
            
            T get(size_t index) {
                assert(index < _data.size());
                return _data[index];
            }
            
            const T get(size_t index) const {
                assert(index < _data.size());
                return _data[index];
            }
            
            void set(T data, size_t index) {
                assert(index < _data.size());
                _data[index] = data;
            }
            
            size_t depth() {return _depth;}
            
            const size_t depth() const {return _depth;}
            
            sbtree &operator=(const sbtree<T> &tree) {
                for (size_t i=0; i<tree.size(); ++i) {
                    if (_data.size() <= i) {
                        _data.push_back(tree.get(i));
                    } else {
                        _data[i] = tree.get(i);
                    }
                }
                _depth = tree.depth();
                return *this;
            }
            
            size_t size() {return _data.size();}
            
            const size_t size() const {return _data.size();}
            
            template <typename P, class operand>
            void walk(P &user_data, operand op) {
                for (size_t i=0; i<_data.size(); ++i) {
                    if(! op(this, user_data))
                        break;
                }
            }
    };
}

#endif
